package com.cyy.test_t_3_;

import java.util.ArrayList;


/**
 * 剑指Offer面试题34
 * 丑数
 * 时间限制：1秒 空间限制：32768K
 * 题目描述
 * 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是
 * 丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑
 * 数。求按从小到大的顺序的第N个丑数。
 */
public class t_34 {

	public static void main(String[] args) {
		System.out.println(GetUglyNumber_Solution(1));
	}
	
	public static int GetUglyNumber_Solution(int index) {
        if(index <= 0)
        	return 0;
        ArrayList<Integer> list=new ArrayList<Integer>();
        list.add(1);
        int i2 = 0, i3 = 0, i5 = 0;
        while(list.size() < index){
        	int pMultipy2 = list.get(i2) * 2;
        	int pMultipy3 = list.get(i3) * 3;
        	int pMultipy5 = list.get(i5) * 5;
        	int min = Min(pMultipy2,pMultipy3,pMultipy5);
        	list.add(min);
        	if(min == pMultipy2) i2 ++;
        	if(min == pMultipy3) i3 ++;
        	if(min == pMultipy5) i5 ++;
        	
        }
        
		return list.get(list.size()-1);
    }
	
	static int Min(int a,int b,int c){
		int min = (a < b)? a : b;
		min = (min < c) ? min : c;
		return min;
	}

}
